package com.colter.project.data.structure.heap;

import java.util.Vector;

/**
 * @author LC
 * 2018/2/3
 */
public abstract class AbstractHeap <E extends  Comparable<E>> extends Vector<E> {

    private void shiftUp(int index){
        E moveElement = elementAt(index);
        if(!hasParent(index)){
            return;
        }
        int pindex = getParentIndex(index);
        E parentElement = elementAt(pindex);
        if(choseLeft(moveElement,parentElement)){
            exchangeValue(index,moveElement,pindex,parentElement);
            shiftUp(pindex);
        }

    }

    private void shiftDown(int index){
        if(!hasLeftSon(index) && !hasRightSon(index)){
            return;
        }

        E moveElement = elementAt(index);
        int lindex = getLeftSonIndex(index);
        int rindex = getRightSonIndex(index);
        if(hasLeftSon(index) && hasRightSon(index)){
            E leftElement = elementAt(lindex);
            E rightElement = elementAt(rindex);
            if(choseLeft(leftElement,rightElement)){
                compareAndExchange(index,moveElement,lindex,leftElement);
                shiftDown(lindex);
            }else{
                compareAndExchange(index,moveElement,rindex,rightElement);
                shiftDown(rindex);
            }

        } else if (hasLeftSon(index)) {
            E leftElement = elementAt(lindex);
            compareAndExchange(index,moveElement,lindex,leftElement);
            shiftDown(lindex);
        }else{
            E rightElement = elementAt(rindex);
            compareAndExchange(index,moveElement,rindex,rightElement);
            shiftDown(rindex);
        }
    }

    protected abstract boolean choseLeft(E leftElement, E rightElement);


    protected  void compareAndExchange(int moveIndex, E moveElement, int compareIndex, E compareElement){
        if(choseLeft(compareElement,moveElement)){
            exchangeValue(moveIndex,moveElement,compareIndex,compareElement);
        }
    }

    @Override
    public synchronized boolean add(E t) {
        super.add(t);
        shiftUp(elementCount-1);
        return true;
    }

    public synchronized E removeAndReturnTop() {
        E result = getTop();
        E last = elementAt(elementCount-1);
        exchangeValue(0,result,elementCount -1,last);
        removeElementAt(elementCount-1);
        shiftDown(0);
        return result;
    }

    public E getTop() {
        if (!isEmpty()){
            return elementAt(0);
        }
        return null;
    }

    protected void exchangeValue(int srcIndex, E srcElement, int destIndex, E destElement){
        assert srcIndex < elementCount && srcIndex >= 0 ;
        assert destIndex < elementCount && destIndex >= 0;
        elementData[srcIndex] = destElement;
        elementData[destIndex] = srcElement;
    }

    private int getLeftSonIndex(int parentIndex){
        assert parentIndex >= 0;
        return parentIndex* 2 + 1;
    }

    private int getRightSonIndex(int parentIndex){
        assert parentIndex >= 0;
        return parentIndex* 2 + 2;
    }

    private int getParentIndex(int sonIndex){
        assert sonIndex >= 1;
        return (sonIndex-1) / 2;
    }

    private boolean hasParent(int sonIndex){
        if(sonIndex < 1){
            return false;
        }
        return true;
    }

    private boolean hasLeftSon(int parentIndex){
        int lindex = getLeftSonIndex(parentIndex);
        return lindex < elementCount;
    }

    private boolean hasRightSon(int parentIndex){
        int rindex = getRightSonIndex(parentIndex);
        return rindex < elementCount;
    }
}
